package com.mccken.practice.top100.Top_30$.Top_31;

import com.mccken.practice.top100.ListNode;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-02-28 21:25
 **/
public class SortList {

	public ListNode sortList(ListNode head) {
		return sortList(head, null);
	}

	private ListNode sortList(ListNode head, ListNode tail) {
		if (head == null) {
			return null;
		}

		if (head.next == tail) {
			head.next = null;
			return head;
		}

		// 快慢指针
		ListNode slow = head, fast = head;
		while (fast != tail && fast.next!=tail) {
			slow = slow.next;
			fast = fast.next.next;
		}
		
		ListNode mid = slow;
		ListNode list1 = sortList(head, mid);
		ListNode list2 = sortList(mid, tail);
		ListNode sorted = merge(list1, list2);
		
		return sorted;
	}

	private ListNode merge(ListNode head1, ListNode head2) {
		ListNode dummyHead = new ListNode(0);
		ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
		while (temp1!=null && temp2!=null) {
			if (temp1.val<=temp2.val) {
				temp.next = temp1;
				temp1 = temp1.next;
			} else {
				temp.next = temp2;
				temp2 = temp2.next;
			}
			temp = temp.next;
		}
		
		if (temp1!=null) {
			temp.next = temp1;
		} else {
			temp.next = temp2;
		}
		
		return dummyHead.next;
	}
	
	

}
